#include<iostream>
using namespace std;
#include<vector>
#include <queue>

int arrx[4] = { 1,-1,0,0 };
int arry[4] = { 0,0,1,-1 };

int maxDistance(vector<vector<int>>& grid) {
	int length1 = grid.size(), length2 = grid[0].size();
	vector<vector<int>> nums;
	vector<int> temp;
	for (int i = 0; i < length2; i++)
	{
		temp.push_back(-1);
	}
	for (int i = 0; i < length1; i++)
	{
		nums.push_back(temp);
	}

	queue < pair<int, int>> q;

	for (int i = 0; i < length1; i++)
	{
		for (int j = 0; j < length2; j++)
		{
			if (grid[i][j] == 1)
			{
				nums[i][j] = 0;
				q.push({ i,j });
			}
		}
	}

	int step = 0;
	while (q.size())
	{
		int sz = q.size();
		
		for (int i = 0; i < sz; i++)
		{
			int x = q.front().first;
			int y = q.front().second;
			q.pop();

			for (int j = 0; j < 4; j++)
			{
				int x1 = x + arrx[j];
				int y1 = y + arry[j];
				if (x1 >= 0 && x1 < length1 && y1 >= 0 && y1 < length2 && nums[x1][y1] == -1)
				{
					nums[x1][y1] = nums[x][y] + 1;
					step = nums[x][y] + 1;
					q.push({ x1,y1 });
				}
			}
		}
	}
	if (step == 0)
	{
		return -1;
	}
	return step;
}

int main()
{
	vector<vector<int>> grid = { {1,0,1},{0,0,0},{1,0,1} };
	maxDistance(grid);
	return 0;
}